package Dijkstra旅途美女搭讪.测试;

//Dijkstra算法来做
import java.util.*;

public class Main1 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 输入第一行数据N M
		int N = sc.nextInt();// N个汽车站
		int M = sc.nextInt();// M条公路
		int[][] weight = new int[N][N];// 保存权值的数组（各个公交站美女数）
		int[] value = new int[N];
		// 输入第二行数据各站的权重
		for (int i = 0; i < N; i++) {
			value[i] = sc.nextInt();
		}
//		int MAX = 10000000;
		int MAX = 100;
		// 初始化weight
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				weight[i][j] = MAX;
			}
		}
		// sc.nextLine();

		// 输入第三行和以后面的数据作为辅助权重数组的下标
		for (int i = 0; i < M; i++) {
			// String[] s=sc.nextLine().split(" ");
			int x = sc.nextInt() - 1;
			int y = sc.nextInt() - 1;
			weight[x][y] = value[y];
			weight[y][x] = value[x];
		}
		for (int i = 0; i < weight.length; i++) {
			weight[i][i] = value[i];
		}

		Tools tools = new Tools();
		tools.print2DArray(weight);

		// weight[0][0]=value[0];
		int[] shortPath = dijkstra(weight, 0);
		int min = shortPath[shortPath.length - 1];
		System.out.println(min);
		sc.close();
	}

	/**
	 * 算法1
	 * 
	 * @param weight
	 * @param a
	 * @return
	 */
	public static int[] dijkstra1(int[][] weight, int a) {

		int MAX = Integer.MAX_VALUE;
		int n = weight.length;
		int[] shortPath = new int[n];
		int[] visited = new int[n];
		// 初始化shortPath
		for (int i = 0; i < n; i++) {
			shortPath[i] = MAX;
		}
		shortPath[0] = weight[0][0];// 还没出发前还有权值
		visited[0] = 1;

		// 核心
		int lastNode = 0;// 初始化最后一个节点指向开始的节点

		for (int count = 1; count < n; count++) {
			int dmin = Integer.MAX_VALUE;
			int k = 0;// 最后节点临时

			for (int i = 0; i < n; i++) {
				if (visited[i] == 0 && shortPath[lastNode] + weight[lastNode][i] < shortPath[i]) {
					shortPath[i] = shortPath[lastNode] + weight[lastNode][i];
				}
				if (visited[i] == 0 && shortPath[i] < dmin) {
					dmin = shortPath[i];
					k = i;
				}
			}

			lastNode = k;
			visited[k] = 1;
		}

		return shortPath;
	}

	/**
	 * 算法2
	 * 
	 * @param weight
	 * @param start
	 * @return
	 */
	public static int[] dijkstra(int[][] weight, int start) {
		int vertexNum = weight.length; // 顶点个数
		int[] shortPath = new int[vertexNum]; // 保存最短路径值
		String[] path = new String[vertexNum]; // 具体路径存在字符串中
		int[] visited = new int[vertexNum]; // 顶点i是否已经求过

		// 初始化
		shortPath[start] = weight[start][start];
		visited[start] = 1;

		int M = 2000000; // 将2000当成无穷大
		// 初始化shortPath数组
		// shortPath[start]=0;
		path[start] = start + "";
		for (int i = 0; i < shortPath.length; i++) {
			if (i != start) {
				shortPath[i] = M;
			}
		}

		int lastNode = start;

		for (int count = 1; count < vertexNum; count++) {
			// 第一次，weight[0][1],weight[0][2],weight[0][3],..weight[0][5]中取最小的
			int dmin = Integer.MAX_VALUE;
			int k = 0;
			for (int i = 0; i < vertexNum; i++) {

				if (visited[i] == 0 && shortPath[lastNode] + weight[lastNode][i] < shortPath[i]) {
					// 拿lastNode到i的值+之前shortPath中lastNode的值 和
					// 对应shortPath比较。小则更新路线
					// 然后再找到一个最小的作为最后的节点
					shortPath[i] = shortPath[lastNode] + weight[lastNode][i];
					// 路线更新存在path数组中
					path[i] = path[lastNode] + "-->" + i;
				}

				if (visited[i] == 0 && shortPath[i] < dmin) {
					dmin = shortPath[i];
					k = i;
				}

			}
			lastNode = k;
			visited[k] = 1;
		}

		// System.out.println(path[path.length-1]);
		return shortPath;
	}
}